//
// Created by Snow on 2023/5/6.
//
//二叉排序树
#include<cstdio>
#include<cstdlib>
#include<cstring>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node//元素类型
{
    KeyType key;//关键字项
    InfoType data;//其他数据域
    struct node *lchild,*rchild;//左右孩子指针
}BSTNode;//二叉排序树结点类型

bool InsertBST(BSTNode *&bt,KeyType k)//在bt中插入一个关键字为k的结点
{
    if(bt==nullptr)//原树为空，新插入的结点为根结点
    {
        bt=(BSTNode*)malloc(sizeof(BSTNode));
        bt->key=k;
        bt->lchild=bt->rchild=nullptr;
        return true;
    }
    else if(k==bt->key)//树中存在相同的关键字，返回假
        return false;
    else if(k<bt->key)
        return InsertBST(bt->lchild,k);//插入到左子树中
    else
        return InsertBST(bt->rchild,k);//插入到右子树中
}

BSTNode *CreateBST(KeyType A[],int n)//创建二叉排序树
{
    BSTNode *bt=nullptr;//初始时bt为空树
    int i=0;
    while(i<n)
    {
        InsertBST(bt,A[i]);//将关键字A[i]插入到二叉排序树bt中
        i++;
    }
    return bt;//返回建立的二叉排序树的根指针
}

void DispBST(BSTNode *bt)//输出一棵二叉排序树
{
    if(bt!=nullptr)
    {
        printf("%d",bt->key);
        if(bt->lchild!=nullptr||bt->rchild!=nullptr)
        {
            printf("(");//有孩子结点时才输出(
            DispBST(bt->lchild);//递归处理左子树
            if(bt->rchild!=nullptr)//有右孩子结点时才输出,
                printf(",");
            DispBST(bt->rchild);//递归处理右子树
            printf(")");//有孩子结点时才输出)
        }
    }
}

BSTNode *SearchBST(BSTNode *bt,KeyType k)// 递归 二叉排序树的查找
{
    if(bt==nullptr||bt->key==k)
        return bt;
    if(k<bt->key)
        return SearchBST(bt->lchild,k);
    else
        return SearchBST(bt->rchild,k);
}

BSTNode *SearchBST1(BSTNode *bt,KeyType k)// 非递归 二叉排序树的查找
{
    BSTNode *p=bt;
    while(p!=nullptr)
    {
        if(p->key==k)//找到关键字为k的结点p时退出循环
            break;
        else if(k<p->key)
            p=p->lchild;
        else
            p=p->rchild;
    }
    return p;//返回查找结果
}

//对于给定的结点p，找出其左子树中的最大结点和右子树的最小结点
KeyType MaxNode(BSTNode *p)//返回二叉排序树p中最大结点关键字
{
    while(p->rchild!=nullptr)
        p=p->rchild;
    return p->key;
}
KeyType MinNode(BSTNode *p)//返回二叉排序树p中最小结点关键字
{
    while(p->lchild!=nullptr)
        p=p->lchild;
    return p->key;
}
void MaxMinNode(BSTNode *p)
{
    if(p!=nullptr)
    {
        if(p->lchild!=nullptr)
            printf("The MaxNode in the left child is %d\n",MaxNode(p->lchild));
        if(p->rchild!=nullptr)
            printf("The MinNode in the right child is %d\n",MinNode(p->rchild));
    }
}

BSTNode *DeleteBST(BSTNode *bt,KeyType k)//在bt中删除关键字为k的结点
{
    if(bt==nullptr)
        return bt;
    BSTNode *p=bt,*f=nullptr;//f指向被删结点p的双亲结点
    while(p!=nullptr)
    {
        if(p->key==k)//找到被删结点p时退出循环
            break;
        f=p;
        if(k<p->key)
            p=p->lchild;
        else
            p=p->rchild;
    }
    if(p==nullptr)//没有找到被删除的结点p，返回bt
        return bt;
    if(p->lchild==nullptr&&p->rchild==nullptr)//情况（1），结点p是叶子结点
    {
        if(p==bt)//p是根节点
            bt=nullptr;
        else//p不是根节点
        {
            if(f->lchild==p)//结点p是结点f的左孩子
                f->lchild=nullptr;
            else//结点p是结点f的右孩子
                f->rchild=nullptr;
            free(p);
        }
    }
    else if(p->rchild==nullptr)//情况（2），结点p只有左子树，没有右子树
    {
        if(f==nullptr)//结点p没有双亲，即p==bt
            bt=bt->lchild;//用bt的左孩子代替bt
        else//结点p存在双亲f
        {
            if(f->lchild==p)//p是f的左孩子
                f->lchild=p->lchild;//用结点p的左孩子代替p
            else//p是f的右孩子
                f->rchild=p->lchild;//用p的左孩子代替p
        }
        free(p);
    }
    else if(p->lchild==nullptr)//情况（3),p只有右子树，没有左子树
    {
        if(f==nullptr)
            bt=bt->rchild;
        else
        {
            if(f->lchild==p)
                f->lchild=p->rchild;
            else
                f->rchild=p->rchild;
        }
        free(p);
    }
    else//情况（4），结点p有左、右子树
    {
        BSTNode *q=p->lchild;//q指向p的左孩子结点
        f=p;//f指向q的双亲结点
        while(q->rchild!=nullptr)//找到结点p的左孩子的最右下结点q（即p的左子树的最大结点）
        {
            f=q;
            q=q->rchild;
        }
        p->key=q->key;//将结点p的值用结点q的值替换
        strcpy(p->data,q->data);
        if(q==f->lchild)//删除结点q
            f->lchild=q->lchild;
        else
            f->rchild=q->lchild;
        free(q);
    }
    return bt;
}

void DestroyBST(BSTNode *&bt)		//销毁二叉排序树bt
{
    if (bt!=nullptr)
    {
        DestroyBST(bt->lchild);
        DestroyBST(bt->rchild);
        free(bt);
    }
}

int main()
{
    BSTNode *bt;
    int n=12,x=46;
    KeyType a[]={25,18,46,2,53,39,32,4,74,67,60,11};
    bt=CreateBST(a,n);
    printf("BST:");
    DispBST(bt);
    printf("\nDelete %d\n",x);
    if(SearchBST(bt,x)!=nullptr)
    {
        DeleteBST(bt,x);
        printf("BST:");
        DispBST(bt);
        printf("\n");
    }
    if(!SearchBST1(bt,1))
        printf("no 1 in the BST\n");
    MaxMinNode(bt);
    DestroyBST(bt);
    return 1;
}